/*
 * SimInfList.h
 *
 *  Created on: 26-nov.-2013
 *      Author: Axel
 */

#ifndef SIMINFLIST_H_
#define SIMINFLIST_H_

#include "searching.h"

/**A class that simulates an infinite list
*  it utilises arrays to store it's data
*/
template <class T>
class InfList {
public:
	InfList(int lenght, bool sort);
	~InfList();

	void add(T x);
	T get(int elem);

	void remove(int x);
	void deleteItem(T x);

	void sort();

	int find(T elem);

	int length() {
		return size;
	}

	T* getList();

	T& operator[] (const int depth)	{
		//if (depth >= 0 && depth < size) {
		return list[depth];
	}

private:
	T* list;
	int size;
	int current;
	bool sorted;

	//helper function to increase size
	T* increaseSize();
};

template <class T>
InfList<T>::InfList(int length, bool sort) {
	list = new T[length];
	size = length;
	current = 0;
	sorted = sort;
}


template <class T>
InfList<T>::~InfList() {
	delete[] list;
}

template <class T>
T* InfList<T>::getList() {
	return list;
}

template <class T>
void InfList<T>::sort() {
	int start = 0, extra = current - 1;
	T hulp;

	while (list[start] < list[current] && start < current)
		start++;

	hulp = list[current];

	while (extra > start) {
		list[extra] = list[extra-1];
		extra--;
	}

	list[start] = hulp;
}

template <class T>
void InfList<T>::deleteItem(T x) {
	int elem = find(x);
	if (elem > -1)
		remove(elem);
}

template <class T>
int InfList<T>::find(T x) {
	return (sorted)? search::binarysearch<T>(x, list, current): search::lineairsearch<T>(x, list, current);
}

template <class T>
void InfList<T>::add(T x) {
	if (current == size) {
		//copy
		list = increaseSize();
	}

	list[current] = x;
	if (sorted)
		sort();
	current++;
}

template <class T>
void InfList<T>::remove(int x) {
	for(int i = x; i<current;i++)
		list[i] = list[i+1];

	current--;
}


template <class T>
T InfList<T>::get(int x) {
	return list[x];
}


template <class T>
T* InfList<T>::increaseSize() {
	const int si = size * 1.5 + 1;
	T* newlist = new T[si];

	for(int i=0;i<size;i++)
		newlist[i] = list[i];

	size *= 1.5;
	delete[] list;

	return newlist;
}

#endif /* SIMINFLIST_H_ */
